/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/segment-tree-build-ii
@Language: C++
@Datetime: 16-02-09 08:30
*/

/**
 * Definition of SegmentTreeNode:
 * class SegmentTreeNode {
 * public:
 *     int start, end, max;
 *     SegmentTreeNode *left, *right;
 *     SegmentTreeNode(int start, int end, int max) {
 *         this->start = start;
 *         this->end = end;
 *         this->max = max;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
    SegmentTreeNode * build(vector<int> &A,int start, int end) {
        // write your code here
        if (start>end)
            return NULL;
        SegmentTreeNode *root = new SegmentTreeNode(start,end,A[start]);
		if (start<end){			
			root->left = build(A,start,(start+end)/2);
	        root->right = build(A,(start+end)/2+1,end);
	        if (root->left) root->max = max(root->max,root->left->max);
	        if (root->right) root->max = max(root->max,root->right->max);
		}
        return root;
    }
public:
    /**
     *@param A: a list of integer
     *@return: The root of Segment Tree
     */
    SegmentTreeNode * build(vector<int>& A) {
        // write your code here
        return build(A,0,A.size()-1);
    }
};